package com.south.base.test.arithmetic;

import java.util.*;

/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * @author Administrator
 * @date 2019/5/22 17:34
 */
public class LongestSubstring {
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || "".equals(s)) {
            return 0;
        } else if (s.length() == 1) {
            return 1;
        }
        char[] charArray = s.toCharArray();
        List<Set<Character>> chars = new ArrayList<>();
        int result = 1;
        for (int i = 0; i < charArray.length; i++) {
            for (int j = 0; j < chars.size(); j++) {
                Set<Character> characterSet = chars.get(j);
                if (characterSet.contains(charArray[i])) {
                    if (characterSet.size() > result) {
                        result = characterSet.size();
                    }
                    chars.remove(j);
                    j--;
                } else {
                    characterSet.add(charArray[i]);
                }
            }
            Set<Character> characterSet = new HashSet<>();
            characterSet.add(charArray[i]);
            chars.add(characterSet);
        }
        for (Set<Character> characterSet : chars) {
            if (characterSet.size() > result) {
                result = characterSet.size();
            }
        }
        return result;
    }

    public static int lengthOfLongestSubstring2(String s) {
        if (s == null || "".equals(s)) {
            return 0;
        } else if (s.length() == 1) {
            return 1;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0;
        int left = 0;
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                left = Math.max(left, map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i), i);
            max = Math.max(max, i - left + 1);
        }
        return max;
    }

    public static int lengthOfLongestSubstring3(String s) {
        if (s == null || "".equals(s)) {
            return 0;
        } else if (s.length() == 1) {
            return 1;
        }
        int i = 0;
        int fromIndex = 0;
        int length = 0;
        int result = 0;
        while (i < s.length()) {
            int pos = s.indexOf(s.charAt(i), fromIndex);
            if (pos < i) {
                if (length > result) {
                    result = length;
                }
                if (result >= s.length() - pos - 1) {
                    return result;
                }
                length = i - pos - 1;
                fromIndex = pos + 1;
            }
            length++;
            i++;
        }
        return length;
    }

    public static void main(String[] args) {
        lengthOfLongestSubstring("dvdf");
    }
}
